package ACM_Brush;

public class Solution004 {
    public static void main(String[] args) {
        int[] nums1 = new int[] { 1, 2, 3, 6, 7 };
        int[] nums2 = new int[] { 2, 3, 4, 4, 4 };
        System.out.println();
        System.out.println(new solution_004().findMedianSortedArrays(nums1, nums2));
    }
}

class solution_004 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if ((m + n) % 2 == 0)
            return (findKSortedArrays(nums1, nums2, (m + n) / 2) + findKSortedArrays(nums1, nums2, (m + n + 1) / 2))
                    / 2;
        else
            return findKSortedArrays(nums1, nums2, (m + n + 1) / 2);
    }

    private double findKSortedArrays(int[] nums1, int[] nums2, int k) {
        int p1 = 0;
        int p2 = 0;
        while (k != 0 && p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1 + k / 2] <= nums2[p2 + k / 2])
                p1 += k / 2;
            else
                p2 += k / 2;
            k -= k / 2;
        }
    }
}